#ifndef ARRAY_HPP_DEF
#define ARRAY_HPP_DEF

#include "allocator.hpp"

/**
 * @brief 支持动态容量扩充 可变长数组
 *
 */
namespace TingSTL {

template <typename T, typename Alloc = allocator<T>>
class array {
public:
    using allocator_type = typename Alloc;

    using value_type = typename allocator_type::value_type;
    using pointer = typename allocator_type::pointer;
    using const_pointer = typename allocator_type::const_pointer;
    using reference = typename allocator_type::reference;
    using const_reference = typename allocator_type::const_reference;

    using difference_type = typename allocator_type::difference_type;
    using size_type = typename allocator_type::size_type;

    using iterator = value_type *;
    using const_iterator = const value_type *;

private:
    pointer _begin;
    pointer _end;
    size_type _cap;

public:
    // /////////////////////////////// 构造析构  复制 移动 copy 等
    // //////////////////
    array() :
        _begin(nullptr), _end(nullptr), _cap(0) {
    }

    explicit array(size_type initCap) :
        _begin(nullptr), _end(nullptr), _cap(0) {
        this->reserve(initCap);
    }

    array(size_type initSize, const_reference initValue) :
        _begin(nullptr), _end(nullptr), _cap(0) {
        if (initSize == 0)
            return;
        _begin = allocator_type::allocate(initSize);
        _end = _begin;
        try {
            for (; initSize > 0; --initSize, ++_end) {
                allocator_type::construct(_end, initValue);
            }
        } catch (...) {
            allocator_type::destroy(_begin, _end);
            allocator_type::deallocate(_begin);
        }
        _cap = initSize;
    }

    ~array() {
        this->destroy();
    }

    array(const array &other) :
        _begin(nullptr), _end(nullptr), _cap(0) {
        if (other._cap == 0)
            return;
        try {
            _end = other._begin;
            _begin = allocator_type::allocate(other._cap);
            for (pointer p = other._begin; p != other._end; ++p, ++_end) {
                { copy(p, _end); }
            }
        } catch (...) {
            allocator_type::destroy(_begin, _end);
            allocator_type::deallocate(_begin);
            throw;
        }
        _cap = other._cap;
    }

    array(array &&other) :
        _begin(nullptr), _end(nullptr), _cap(0) {
        this->swap(other);
    }

    array &operator=(array other) {
        this->swap(other);
        return *this;
    }
    // /////////////////////////////// 容量，数据 相关 //////////////////////////////

    // 当前容器元素个数
    inline size_type size() const {
        if (_begin == nullptr)
            return 0;
        return _end - _begin;
    }

    inline size_type capacity() {
        return _cap;
    }

    inline bool empty() const {
        return _begin == _end;
    }

    // 调整容量
    void reserve(size_type newCap) {
        if (newCap == _cap)
            return;

        // 清空
        if (newCap == 0) {
            if (_cap != 0)
                this->destroy();
            return;
        }

        pointer moveEnd =
            newCap >= size() ? _end : _begin + newCap; // 需要移动的元素 结束点
        pointer newBegin = nullptr;
        pointer newEnd = nullptr;
        try {
            newBegin = allocator_type::allocate(newCap);
            newEnd = newBegin;
            for (pointer p = _begin; p != _end; ++p, ++newEnd) {
                move(p, newEnd);
            }
        } catch (...) {
            allocator_type::destroy(newBegin, newEnd);
            allocator_type::deallocate(newBegin);
            throw;
        }
        allocator_type::destroy(_begin, _end);
        allocator_type::deallocate(_begin);
        _begin = newBegin;
        _end = newEnd;
        _cap = newCap;
    }

    int insert(size_type pos, value_type &&v) {
        return (
            int)(this->emplace(_begin + pos, std::forward<value_type>(v)) - _begin);
    }

    template <typename... Args>
    iterator emplace(const const_iterator &pos, Args &&...args) {
        // 判定 插入范围
        TING_ASSERT(pos != nullptr && pos <= _end && pos >= _begin,
                    "array emplace pos outside range");
        difference_type distance = _cap == 0 ? 0 : pos - _begin;
        // 扩容
        if (size() == _cap)
            this->reallocate(1);
        auto place = _begin + distance; // fix: 容器重新分配内存，指针失效
        // 将插入位置之后的元素 向后移动
        for (auto movePos = _end - 1; movePos >= place; --movePos) {
            move(movePos, movePos + 1);
        }

        // 插入元素
        allocator_type::construct(place, std::forward<Args>(args)...);
        ++_end;
        return place;
    }

    // 返回删除位置的下一个位置的迭代器
    iterator erase(const iterator &pos) {
        // 判定 删除范围范围
        TING_ASSERT(pos != nullptr && pos < _end && pos >= _begin,
                    "array emplace pos outside range");
        allocator_type::destroy(pos);
        for (auto movePos = pos; movePos < _end; ++movePos) {
            move(movePos + 1, movePos);
        }
        --_end;
        return _end == pos ? _end - 1 : pos;
    }

    void remove(size_t pos) {
        erase(_begin + pos);
    }

    template <typename... Args>
    iterator emplace_back(Args &&...args) {
        if (size() == _cap)
            this->reallocate(1);
        allocator_type::construct(_end, std::forward<Args>(args)...);
        ++_end;
        return _end - 1;
    }

    iterator push(const value_type &v) {
        return emplace_back(v);
    }

    value_type pop() {
        TING_ASSERT(this->empty(), "array is empty , cant pop");
        --_end;
        value_type ret = std::move(*_end);
        allocator_type::destroy(_end);
        return ret;
    }

    void clear() {
        if (empty())
            return;

        allocator_type::destroy(_begin, _end);
        _end = _begin;
    }

    // /////////////////////////////// 算法相关 //////////////////////////////
    int findIndex(const T &target, int begin = 0) const {
        if (_begin == nullptr || size() <= begin)
            return -1;

        pointer p = _begin + begin;
        for (; p != _end; ++p) {
            if (*p == target)
                return static_cast<int>(p - _begin);
        }
        return -1;
    }

    // /////////////////////////////// 迭代器相关 //////////////////////////////

    inline iterator begin() noexcept {
        return _begin;
    }

    inline iterator begin() const noexcept {
        return _begin;
    }

    inline iterator end() noexcept {
        return _end;
    }

    inline iterator end() const noexcept {
        return _end;
    }

    inline const_iterator cbegin() const noexcept {
        return _end;
    }

    inline const_iterator cend() const noexcept {
        return _end;
    }

    void swap(array &other) {
        std::swap(other._begin, _begin);
        std::swap(other._end, _end);
        std::swap(other._cap, _cap);
    }

    T &operator[](size_t pos) {
        TING_ASSERT(pos < size(), "Access array out off range");
        return _begin[pos];
    }

    // /////////////// 输出相关 ，调试使用 //////////////
    // 输出
    friend std::ostream &operator<<(std::ostream &os, const array &arr) {
        for (auto begin = arr._begin; begin < arr._end; ++begin) {
            os << *begin;
        }
        return os;
    }

private:
    // ///////////////////// 内存相关 ////////////////////////
    void tryInit(size_type cap) noexcept {
        _begin = nullptr;
        _end = nullptr;
        _cap = 0;
        if (cap == 0)
            return;
        try {
            _begin = allocator_type::allocate(cap);
            _end = _begin;
            _cap = cap;
        } catch (...) {
            TING_ASSERT(false, "allocate Memory Fail");
        }
    }

    size_type reallocate(size_type needCap) {
        auto newCap = std::max(_cap + needCap, _cap * 2);
        this->reserve(newCap);
        return newCap;
    }

    void destroy() {
        allocator_type::destroy(_begin, _end);
        allocator_type::deallocate(_begin);
        _begin = nullptr;
        _end = nullptr;
        _cap = 0;
    }

    static void copy(pointer src, pointer dst) {
        allocator_type::construct(dst, *src);
        allocator_type::destroy(src);
    }

    static void move(pointer src, pointer dst) {
        allocator_type::construct(dst, std::move(*src));
        allocator_type::destroy(src);
    }
};
} // namespace TingSTL

namespace std {
template <typename T, typename Alloc>
void swap(TingSTL::array<T, Alloc> &lhs, TingSTL::array<T, Alloc> &rhs) {
    lhs.swap(rhs);
}
} // namespace std

#endif // ARRAY_HPP_DEF